Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Fair Distribution of Cookies

Problem Statement

You are given an array of integers cookies, where cookies[i] represents the count of cookies in the ith bag, and integer k that represents the number of children. You must divide these bags among k children such that every bag goes entirely to one child, with no splitting of the contents.

The maximum number of total cookies obtained by a single child in the distribution is called the unfairness of the distribution.

Return the minimum unfairness of all distributions.

Examples

  1. Example 1:

    • Input: cookies = [5,6,7,3,4], k = 2
    • Expected Output: 13
    • Justification: The most balanced way to distribute the cookies is to give bags [5,7] to one child and [6,3,4] to the other, resulting in one child getting 13 cookies and the other getting 12. The maximum number of cookies received by a child is 13, which is the minimal unfairness possible here.
  2. Example 2:

    • Input: cookies = [1,2,3,4,5,6,7,8], k = 3
    • Expected Output: 12
    • Justification: An optimal distribution would give bags [4, 8], [5, 7], and [1, 2, 3, 6] to the three children. This way, the maximum cookies any child gets is 12, which is the best minimal unfairness achievable with this setup.
  3. Example 3:

    • Input: cookies = [10,10,10,10], k = 4
    • Expected Output: 10
    • Justification: Since there are equal numbers of cookies in each bag and the same number of children as there are bags, the fairest distribution is straightforward: each child gets one bag. The maximum cookies received by any child is 10, which is the lowest possible unfairness.

Solution

To solve this problem, we approach it with a backtracking algorithm that systematically explores all possible distributions of cookies to the children. The algorithm aims to minimize the maximum number of cookies received by any child. By considering each bag of cookies one at a time and deciding which child to give it to, we can explore the entire space of distributions.

The reason this approach is effective is that it allows us to exhaust all possibilities and choose the one with the least unfairness. It's akin to searching through a tree where each node represents a decision (which child gets the next bag of cookies), and we are trying to find the leaf node with the minimum value of the maximum cookies received by any child. The backtracking aspect is crucial because it enables us to undo decisions and explore different paths in the search tree, ensuring we find the optimal solution.

Step-by-Step Algorithm

  1. Initialize Variables and Start the Process:

    • Initializes the process by calling the backtrack method with the initial state: the cookies array, index 0 (starting point), an array to keep track of the total cookies each child has received (initialized with zeros and of length k), and Integer.MAX_VALUE (or an equivalent large value) to represent the initial minimal unfairness.
  2. Base Case Check:

    • Inside the backtracking function, check if the current index matches the length of the cookies array. If it does, calculate the current distribution's unfairness by finding the maximum value in the children array (the most cookies any child has received). Compare this with the current minimal unfairness and update the minimal unfairness to be the smaller of the two. Return this updated minimal unfairness value.
  3. Recursive Exploration:

    • If the base case condition is not met, iterate over each child, attempting to distribute the current cookie to each child one by one. For each child:
      • Add the number of cookies in the current bag (indicated by the current index) to the total cookies of the child being considered.
      • Recursively call the backtrack function with the next index (current index + 1) to consider the next bag of cookies, and pass the updated minimal unfairness value. This recursive call will return an updated minimal unfairness, which considers the addition of the current cookie to the current child.
      • Subtract the number of cookies in the current bag from the total cookies of the child being considered to undo the current distribution step (backtrack), enabling the exploration of other distribution possibilities.
  4. Return the Result:

    • The backtrack function returns the minimal unfairness value after exploring all possible distributions. This value is then returned by the distributeCookies method as the final result, representing the minimal unfairness achievable for the given set of cookies and number of children.

Algorithm Walkthrough

Let's consider the Input: cookies = [5,7,6,3,4], k = 2

  1. Initial Call:
    • The distributeCookies method is called with cookies = [5,7,6,3,4] and k = 2.
    • This method initializes a children array with 2 elements (for 2 children), both set to 0, indicating that initially, no child has been given any cookies.
    • It then calls the backtrack method with the initial index of 0 and an initial minimal unfairness value set to Integer.MAX_VALUE.

2. Start Recursive Exploration with the First Cookie:

  • Index 0, Cookies[0] = 5:
    • First child (children[0]): Attempt to give them the first cookie bag (5 cookies).
      • Update children to [5, 0].
      • Call backtrack with next index (1).

3. Continue to Second Cookie:

  • Index 1, Cookies[1] = 7:
    • First child: Attempt to give them the second cookie bag (6 cookies).
      • Update children to [12, 0].
      • Call backtrack with next index (2).

4. Continue to Third Cookie:

  • Index 2, Cookies[2] = 6:
    • First child: Attempt to give them the third cookie bag (7 cookies).
      • Update children to [18, 0].
      • Call backtrack with next index (3).

5. Continue to Fourth Cookie:

  • Index 3, Cookies[3] = 3:
    • First child: Attempt to give them the fourth cookie bag (3 cookies).
      • Update children to [21, 0].
      • Call backtrack with next index (4).

6. Continue to Fifth Cookie:

  • Index 4, Cookies[4] = 4:
    • First child: Attempt to give them the fifth cookie bag (4 cookies).
      • Update children to [25, 0]. This is the maximum unfairness when all cookies are given to the first child.
      • No more cookies left. Compute unfairness (25) and backtrack. Now, minUnfairness = 25. 7. Backtrack to index 3:
  • Remove the fifth cookie bag from the first child, backtrack to fourth cookie.
  • Now, attempt to give the fifth cookie bag (4 cookies) to the second child.
  • Update children to [21, 4].
  • Now, index = 5. So, Update minUnfairness. Now, minUnfairness = 21.

7. Backtrack to index 2:

  • Remove the fourth cookie bag from the first child, backtrack to third cookie.
  • Now, attempt to give the fourth cookie bag (3 cookies) to the second child.
  • Update children to [18, 7] when we reach to index 5.
  • Update minUnfairness when we reach to index 5. Now, minUnfairness = 18.

7. Backtrack to index 2:

  • Remove the third cookie bag from the first child, backtrack to second cookie.
  • Now, attempt to give the third cookie bag (6 cookies) to the second child.
  • Update children to [12, 12] when we reach to index 5.
  • Update minUnfairness when we reach to the index 5. Now, minUnfairness = 12.

8. Systematically Explore All Combinations:

  • Continue the systematic exploration by shifting the distribution of cookies among the children at every level of recursion, ensuring every possible combination of distributions is considered. For each configuration, update the children array, compute unfairness, and compare it to the current minimum unfairness to potentially update it.

9. Return the Result:

  • The distributeCookies function ultimately returns the minimal unfairness value, which is 12.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Time Complexity: , where n is the number of cookies (or bags) and k is the number of children. This is because, for each cookie, we have k choices (which child to give the cookie to), leading to possible distributions to explore through backtracking.

Space Complexity

  • Space Complexity: , where n is the depth of the recursion tree (or the number of cookies). This space is used to store the recursion call stack. The auxiliary space used to store the children's cookies count is , but since k ≤ n (in most practical scenarios, you wouldn't have more children than cookies), the dominating factor is .
Fair Distribution of Cookies (medium)
Find Leaves of Binary Tree (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity